1. Field of the Invention
The present invention relates generally to image processing, and more particularly to forming a composite image pixel from two separate images. Still more particularly, the present invention is a circuit and method for forming a composite image pixel by blending pixels from each separate image.
2. Description of the Background Art
An image to be displayed on a computer screen or video monitor comprises an array of picture elements (pixels), where each pixel comprises a binary signal corresponding to a plurality of characteristics such as color or shading information. Often, two or more images must be combined via a blending operation to form a single composite image. In forming the composite image, a first image is designated as a foreground image, and a second image is designated as a background image. The foreground image and the background image are then combined on a pixel-by-pixel basis relative to a blending factor. The blending factor specifies the extent to which a given foreground image pixel is weighted relative to the corresponding background image pixel in producing the composite image pixel. The foreground image pixel is represented by an N-bit foreground pixel signal that is considered to be either a fixed-point fractional value between 0 and 1, or an integral value ranging from 0 to (2.sup.N -1). The background image pixel and the composite image pixel are likewise represented by N-bit background pixel and N-bit composite pixel signals, respectively. The fundamental operations required in blending comprise: scaling the foreground pixel signal by the blending factor; scaling the background pixel signal by one minus the blending factor; and forming the composite pixel signal by combining the appropriately scaled foreground and background pixel signals. Each scaling in the blending comprises a multiplication operation, and the signal combination comprises an addition operation.
In certain image processing applications, the amount of time available for performing the calculations required for realistically displaying an image transformation is severely limited. Current technology has made image sizes of 1024.times.768, or 786,432 pixels commonplace. Blending the pixels of two images to form a composite image must be done on a pixel-by-pixel basis and therefore requires millions of computational operations. Computational time constraints are particularly severe in interactive computer graphics situations, in which actions performed by a computer user influence or direct entire sequences of displayed images. Blending is frequently required in such situations, and must be performed as quickly as possible.
The blending factor is typically represented as an M-bit signal having a fixed-point fractional value between 0 and 1. An alternative integer-based representation of the blending factor comprises the ratio of a first M-bit blending factor signal corresponding to an integer between 0 and (2.sup.M -1), and a second M-bit blending factor signal corresponding to the largest signal value that can be represented with M bits, namely (2.sup.M -1). Using this representation of the blending factor, the operations required to implement a given blending comprise: multiplication of the binary foreground pixel signal by the first blending factor signal; multiplication of the background pixel signal by the second blending factor signal minus the first blending factor signal; addition of the appropriately multiplied foreground and background pixel signals; and normalization of the combination relative to the second blending factor signal. Thus, each pixel blending requires a total of four operations.
Since the second blending factor signal corresponds to a value of (2.sup.M -1), the normalization step within the four operations indicated above is a division. A division operation is much slower than the scaling and additive operations performed during the blending, and is therefore undesirable. The prior art has attempted to solve this problem by using an approximate normalization signal corresponding to a value of 2.sup.M. Normalization by 2.sup.M simply corresponds to an M-bit right shift applied to a binary signal, which can be performed quickly. However, this approximation introduces an error into the blended pixel. When multiple blendings occur, such errors can accumulate rapidly. This in turn leads to an inaccurate composite pixel signal that has an undesirable appearance when displayed.
Referring now to FIG. 1, a prior art circuit used to form a composite pixel through pixel blending is shown. The prior art circuit accepts only two input signals, whereas blending requires three input signals corresponding to the foreground pixel signal, the background pixel signal, and the blending factor signal. Therefore, the circuit of FIG. I requires that the multiplications in the blending are performed separately. Each multiplication generates an intermediate result. For example, a first intermediate result is generated after the foreground pixel signal is multiplied by the first blending factor signal. A second intermediate result is generated after the multiplication of the background pixel signal by the second blending factor signal.
In the generation of the first intermediate result, the prior art circuit uses a bit selector to select a first bit within the blending factor signal. The selected bit is used in a logical AND operation to produce a first partial product signal comprising the foreground pixel signal. A shifter next shifts the first partial product signal according to the position the selected bit occupies within the blending factor signal, after which the first partial product signal is stored in a first accumulator. The bit selector and the shifter are both controlled by a counter, where the output of the counter indicates which bit within the blending factor signal is the selected bit. After the first partial product signal has been accumulated, the counter is incremented and another bit within the blending factor signal becomes the selected bit. Each bit within the blending factor signal is used in the manner described above to generate a corresponding partial product signal. The first accumulator combines each newly-generated partial product signal to form a sum of the previously generated partial product signals. Therefore, if the blending factor signal comprises M bits, the first intermediate result is M partial product signals that have been appropriately shifted and accumulated. After each of the M partial product signals have been shifted and accumulated to form the first intermediate result, the first intermediate result is stored in a second accumulator.
Next, the background pixel signal and the second blending factor signal are applied to the prior art circuit to generate a second intermediate result. The generation of the second intermediate result occurs in the same manner as the generation of the first intermediate result. After the second intermediate result has been stored in the first accumulator, it is accumulated in the second accumulator. The contents of the second accumulator thus comprise the foreground pixel signal multiplied by the first blending factor signal, plus the background pixel signal multiplied by the second blending factor signal.
In the circuit of the prior art, each multiplication is performed separately, one after the other. Then the signals generated by each multiplication are combined. Furthermore, each multiplication comprises many operations. Therefore, performing each multiplication sequentially requires significantly more computation time than if each multiplication were performed simultaneously. Simultaneous performance of each multiplication is possible if all the circuit elements were duplicated and added to the circuit of FIG. 1, thereby creating a circuit which could multiply the first blending factor signal by the foreground pixel signal concurrent with the multiplication of the second blending factor signal by the background pixel signal. However, the addition of such circuit elements greatly increases the area of the circuit, the circuit wiring complexity, and the cost of circuit manufacture.
What is needed is an apparatus and method for forming a composite image pixel through pixel blending that requires significantly less computation time to form a composite image pixel than in prior art implementations, maintains an acceptable degree of composite pixel signal accuracy, and simultaneously performs blending operations without adversely affecting implementation complexity or cost.